package com.xinpan.exercise;

public class NQueens2 {
    public int totalNQueens(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(n == 0)
            return 0;
        
        int[] board = new int[n];
        int count = 0;
        for(int i = 0; i < n; i++)
        {
            board[0] = i;
            count += subSolve(board, n, 1);
        }
        return count;
    }
    
    public int subSolve(int[] board, int n, int r)
    {
        if(r == n)
            return 1;
        
        int count = 0;
        for(int i = 0; i < n; i++)
        {
            if(isSafe(board, n, i, r))
            {
                board[r] = i;
                count += subSolve(board, n, r+1);
            }
        }
        return count;
    }
    
    public boolean isSafe(int[] board, int n, int c, int r)
    {
        boolean res = true;
        
        for(int i = 0; i < r; i++)
        {
            if(board[i] == c ||
                board[i] + (r-i) == c ||
                board[i] - (r-i) == c)
            {
                res = false;
                break;
            }
        }
        return res;
    }
}
